package com.sukaiyi.leetcode._983minimum_cost_for_tickets;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * @author sukaiyi
 * @date 2020/05/06
 * @see <a href="https://leetcode-cn.com/problems/minimum-cost-for-tickets/>题目地址</a>
 */
public class Solution {

    @Test
    public void test() {
        assertEquals(2, mincostTickets(new int[]{1}, new int[]{2, 7, 15}));
        assertEquals(4, mincostTickets(new int[]{1, 2}, new int[]{2, 7, 15}));
        assertEquals(11, mincostTickets(new int[]{1, 4, 6, 7, 8, 20}, new int[]{2, 7, 15}));
        assertEquals(17, mincostTickets(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31}, new int[]{2, 7, 15}));
        assertEquals(423, mincostTickets(new int[]{1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 24, 25, 27, 28, 29, 30, 31, 34, 37, 38, 39, 41, 43, 44, 45, 47, 48, 49, 54, 57, 60, 62, 63, 66, 69, 70, 72, 74, 76, 78, 80, 81, 82, 83, 84, 85, 88, 89, 91, 93, 94, 97, 99}, new int[]{9, 38, 134}));
    }

    public int mincostTickets(int[] days, int[] costs) {
        Map<Integer, Integer> table = new HashMap<>();
        return mincostTickets(days, costs, 0, table, min(costs));
    }

    public int mincostTickets(int[] days, int[] costs, int start, Map<Integer, Integer> table, int minCost) {
        if (days.length - start < 1) {
            return 0;
        }
        if (days.length - start == 1) {
            return minCost;
        }
        if (table.get(start) != null) {
            return table.get(start);
        }
        int costIf1 = costs[0] + mincostTickets(days, costs, start + 1, table, minCost);
        int i = start;
        for (; i < days.length && days[start] + 7 > days[i]; i++) ;
        int costIf7 = costs[1] + mincostTickets(days, costs, i, table, minCost);
        i = start;
        for (; i < days.length && days[start] + 30 > days[i]; i++) ;
        int costIf30 = costs[2] + mincostTickets(days, costs, i, table, minCost);

        int min = min(costIf1, costIf7, costIf30);
        table.put(start, min);
        return min;
    }

    public int min(int... nums) {
        assert nums != null;
        assert nums.length > 0;
        int min = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (min > nums[i]) {
                min = nums[i];
            }
        }
        return min;
    }

}
